# 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
#  子数组 是数组中的一个连续部分。
#
#  示例 1：
# 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
# 输出：6
# 解释：连续子数组[4,-1,2,1] 的和最大，为6 。
#
#  示例 2：
# 输入：nums = [1]
# 输出：1
#
#  示例 3：
# 输入：nums = [5,4,-1,7,8]
# 输出：23
import math
from typing import List


class Solution:
    """
    前缀和思想
    nums[i] ~ nums[j] 的和要最大
    转化成前缀和即 pre_sum[i] - pre_sum[j - 1]最大
    固定i 那么就要pre_sum[j - 1]尽量小
    所以需要再维护一个pre_sum_mins 表示数组前 i 项的最小和
    """
    def maxSubArray3(self, nums: List[int]) -> int:
        # pre_sums[i] 数组的前 i 项和(前缀和); pre_sum_mins[i] 数组前 i 项的最小和
        pre_sums, pre_sum_mins, res = [0] * (len(nums) + 1), [0] * (len(nums) + 1), -math.inf
        for i in range(1, len(nums) + 1):
            pre_sums[i] = pre_sums[i - 1] + nums[i - 1]
            pre_sum_mins[i] = min(pre_sum_mins[i - 1], pre_sums[i])
        # 在 i 之前(0 ~ i - 1)中找一个 j， 使得 pre_sum[i] - pre_sum[j - 1]
        for i in range(1, len(nums) + 1):
            res = max(res, pre_sums[i] - pre_sum_mins[i - 1])
        return res

    def maxSubArray2(self, nums: List[int]) -> int:
        """
        分治
        分：将数组递归拆分成左右子区间，直到每个区间的长度为1为止
        合：将[l,m] 左区间的信息和 [m+1,r] 右区间的信息合并成区间 [l,r] 的信息
          需要维护的信息有
          [l,r] 内以 l 为左端点的最大子段和(lSum)
          [l,r] 内以 r 为右端点的最大子段和(rSum)
          [l,r] 内的最大子段和(mSum)
          [l,r] 的区间和(aSum)
        :param nums:
        :return:
        """

        # 该函数返回的结果status(四个值的元组)中
        # status[0] 表示 [l,r] 内以 l 为左端点的最大子段和(lSum)
        # status[1] 表示 [l,r] 内以 r 为右端点的最大子段和(rSum)
        # status[2] 表示 [l,r] 内的最大子段和(mSum)
        # status[3] 表示 [l,r] 的区间和(aSum) (即 左子区间的 aSum 加上 右子区间 的 aSum)
        def maxSubArrayRange(left, right) -> tuple:  # 查询 nums 序列[l,r] 区间内的最大子段和
            if left == right:
                return nums[left], nums[left], nums[left], nums[left]
            mid = (left + right) >> 1
            # 递归进行拆分(分)
            leftStatus = maxSubArrayRange(left, mid)
            rightStatus = maxSubArrayRange(mid + 1, right)

            def mergeLeftRightStatus(lStatus: tuple, rStatus: tuple) -> tuple:  # 合并左右区间信息的函数
                aSum = lStatus[3] + rStatus[3]
                lSum = max(lStatus[0], lStatus[3] + rStatus[0])
                rSum = max(rStatus[1], rStatus[3] + lStatus[1])
                mSum = max(lStatus[2], rStatus[2], lStatus[1] + rStatus[0])
                return lSum, rSum, mSum, aSum

            # 合并得到结果(合)
            return mergeLeftRightStatus(leftStatus, rightStatus)

        return maxSubArrayRange(0, len(nums) - 1)[2]

    def maxSubArray1(self, nums: List[int]) -> int:
        """
        解法一:动态规划
        dp[i]表示数组前 i + 1个元素的最大连续子序和
        :param nums:
        :return:
        """
        # 使用数组记录
        # dp = [nums[0]]  # dp[i]表示数组前 i + 1个元素的连续最大子序和
        # res = nums[0]
        # for i in range(1, len(nums)):
        #     dp.append(max(dp[-1] + nums[i], nums[i]))
        #     res = max(dp[-1], res)

        # 使用一个临时变量记录(因为每个状态只与前一个状态有关)
        pre, res = 0, nums[0]
        for num in nums:
            pre = max(pre + num, num)
            res = max(pre, res)

        return res

    def maxSubArray(self, nums: List[int]) -> int:
        return self.maxSubArray3(nums)


if __name__ == "__main__":
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    nums = [-2, 1]
    print(Solution().maxSubArray(nums))
